// 1. 钢条切割问题
// 1.1 自顶向下递归实现
pub fn cut_rod(p: &Vec<u32>, n: usize) -> u32 {
    println!("----递归  {}", n);
    if n == 0 {
        return 0;
    }
    let mut q = u32::MIN;
    for i in 0..n {
        println!("+++  {}  +++", i);
        q = u32::max(q, p[i] + cut_rod(p, n - i - 1));
        println!("--- q : {}", q);
    }
    return q;
}

// 1.2 动态规划--自顶向下
pub fn memoized_cut_rod(p: &Vec<u32>, n: usize) -> u32 {
    let mut r = vec![u32::MIN; n];
    return memoized_cut_rod_aux(p, n, &mut r);
}
fn memoized_cut_rod_aux(p: &Vec<u32>, n: usize, r: &mut Vec<u32>) -> u32 {
    if n > 0 && r[n - 1] != u32::MIN {
        return r[n - 1];
    }
    let mut q = u32::MIN;
    if n == 0 {
        r[0] = 0;
    } else {
        for i in 1..=n {
            q = u32::max(q, p[i - 1] + memoized_cut_rod_aux(p, n - i, r));
        }
        r[n - 1] = q;
    }
    println!("{:?}", r);
    return q;
}
// 1.3 动态规划--自底向上
pub fn bottom_up_cut_rod(p: &Vec<u32>, n: usize) -> u32 {
    println!("{:?}", p);
    let mut r = vec![u32::MIN; n + 1];
    r[0] = 0;
    for j in 0..=n {
        let mut q = u32::MIN;
        for i in 0..j {
            q = u32::max(q, p[i] + r[j - i - 1]);
        }
        r[j] = q;
        println!("{:?}", r);
    }
    return r[n];
}

// 1.4 重构解
pub fn extended_bottom_up_cut_rod(p: &Vec<u32>, n: usize) -> (u32, u32) {
    let mut r = vec![u32::MIN; n + 1];
    let mut s = vec![u32::MIN; n + 1];
    r[0] = 0;
    for j in 0..=n {
        let mut q = u32::MIN;
        for i in 0..j {
            if q < p[i] + r[j - i - 1] {
                q = p[i] + r[j - i - 1];
                s[j] = (i + 1) as u32;
            }
        }
        r[j] = q;
    }
    println!("r: {:?}\ns: {:?}", r, s);
    (r[n], s[n])
}
/*
    let p = vec![1, 5, 8, 9, 10, 17, 17, 20, 24, 30];
    let (q, s) = extended_bottom_up_cut_rod(&p, 9);
    println!("q: {}, s: {}", q, s);
*/

// 2. 矩阵链乘法
pub struct Matrix {
    row: usize,
    column: usize,
}
impl Matrix {
    pub fn new(r: usize, c: usize) -> Self {
        Matrix { row: r, column: c }
    }
}
// 2.1 自底向上
pub fn matrix_chain_order(p: &Vec<Matrix>) -> (Vec<Vec<u32>>, Vec<Vec<usize>>) {
    let n = p.len();
    let mut m = vec![vec![u32::MAX; n]; n];
    let mut s = vec![vec![0_usize; n]; n];
    let mut q;
    let mut j;
    for l in 2..=n {
        for i in 0..(n - l + 1) {
            j = i + l - 1;
            for k in i..j {
                q = m[i][k] + m[k + 1][j] + (p[i].row * p[k].column * p[j].column) as u32;
                if q < m[i][j] {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
    (m, s)
}
pub fn print_optimal_parens(s: &Vec<Vec<usize>>, i: usize, j: usize) {
    if i == j {
        print!(" A{} ", i + 1);
    } else {
        print!("(");
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j] + 1, j);
        print!(")");
    }
}

/*
    let p = vec![Matrix::new(30, 35), Matrix::new(35, 15), Matrix::new(15, 5), Matrix::new(5, 10), Matrix::new(10, 20), Matrix::new(20, 25)];
    let (q, s) = matrix_chain_order(&p);
    for i in q.iter() {
        println!("{:>5?}", i);
    }
    println!("-----------------");
    for i in s.iter() {
        println!("{:?}", i);
    }
    println!("-----------------");
    print_optimal_parens(&s, 0, p.len()-1);
*/

// 2.2 自顶向下
pub fn memoized_matrix_chain(p: &Vec<Matrix>) -> u32 {
    let n = p.len();
    let mut m = vec![vec![u32::MAX; n]; n];
    return lookup_chain(&mut m, p, 0, n - 1);
}
pub fn lookup_chain(m: &mut Vec<Vec<u32>>, p: &Vec<Matrix>, i: usize, j: usize) -> u32 {
    if m[i][j] < u32::MAX {
        return m[i][j];
    }
    if i == j {
        m[i][j] = 0;
    } else {
        for k in i..j {
            let q = lookup_chain(m, p, i, k)
                + lookup_chain(m, p, k + 1, j)
                + (p[i].row * p[k].column * p[j].column) as u32;
            if q < m[i][j] {
                m[i][j] = q;
            }
        }
    }
    m[i][j]
}
/*
    let p = vec![Matrix::new(30, 35), Matrix::new(35, 15), Matrix::new(15, 5), Matrix::new(5, 10), Matrix::new(10, 20), Matrix::new(20, 25)];
    let m = memoized_matrix_chain(&p);
    println!("m : {:?}", m);
*/

// 3. 最长公共子序列
pub fn lcs_length(x: &Vec<char>, y: &Vec<char>) -> (Vec<Vec<u32>>, Vec<Vec<u8>>) {
    let m = x.len();
    let n = y.len();
    let mut b = vec![vec![0_u8; n]; m];
    let mut c = vec![vec![0_u32; n + 1]; m + 1];
    for i in 1..=m {
        for j in 1..=n {
            if x[i - 1] == y[j - 1] {
                c[i][j] = c[i - 1][j - 1] + 1;
                b[i - 1][j - 1] = 1_u8;
            } else if c[i - 1][j] >= c[i][j - 1] {
                c[i][j] = c[i - 1][j];
                b[i - 1][j - 1] = 2_u8;
            } else {
                c[i][j] = c[i][j - 1];
                b[i - 1][j - 1] = 3_u8;
            }
        }
    }
    (c, b)
}
pub fn print_lcs(b: &Vec<Vec<u8>>, x: &Vec<char>, i: usize, j: usize) {
    if i == 0 || j == 0 {
        if b[i][j] == 1 {
            print!("{} ", x[i]);
        }
        return;
    }
    if b[i][j] == 1 {
        print_lcs(b, x, i - 1, j - 1);
        print!("{} ", x[i]);
    } else if b[i][j] == 2 {
        print_lcs(b, x, i - 1, j);
    } else {
        print_lcs(b, x, i, j - 1);
    }
}
/*
    let x = vec!['A', 'B', 'C', 'B', 'D', 'A', 'B'];
    let y = vec!['B', 'D', 'C', 'A', 'B', 'A'];
    let (c, b) = lcs_length(&x, &y);
    for i in c {
        println!("{:?}", i);
    }
    println!("------------------");
    for i in b.clone() {
        println!("{:?}", i);
    }
    println!("------------------");
    print_lcs(&b, &x, x.len()-1, y.len()-1);
*/

// 4. 最优二叉搜索树
pub fn optimal_bst(p: &Vec<f32>, q: &Vec<f32>, n: usize) -> (Vec<Vec<f32>>, Vec<Vec<usize>>) {
    let mut e = vec![vec![0.0_f32; n + 1]; n + 2];
    let mut w = vec![vec![0.0_f32; n + 1]; n + 2];
    let mut root = vec![vec![0_usize; n]; n];
    let mut j;
    let mut t;
    for i in 1..=(n + 1) {
        e[i][i - 1] = q[i - 1];
        w[i][i - 1] = q[i - 1];
    }
    for l in 1..=n {
        for i in 1..=(n - l + 1) {
            j = i + l - 1;
            e[i][j] = f32::MAX;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            for r in i..=j {
                t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                if t < e[i][j] {
                    e[i][j] = t;
                    root[i - 1][j - 1] = r;
                }
            }
        }
    }
    (e, root)
}
/*
    let p = vec![0.0, 0.15, 0.10, 0.05, 0.10, 0.20];
    let q = vec![0.05, 0.10, 0.05, 0.05, 0.05, 0.10];
    let (e, root) = optimal_bst(&p, &q, p.len()-1);
    for i in e.iter() {
        print!("[");
        for j in i.iter() {
            print!("{:.2}, ", j);
        }
        println!("]");
    }
    println!("------------------");
    for i in root.iter() {
        println!("{:?}", i);
    }
*/
